// 输入：一个无序待排序的数组
// f:递归来实现快速排序
// 输出：返回排序好的数组
function quickSort(arr) {
    //1.处理意外情况
    if (arr.length === 0) { return [] }
    // 2.借助开辟新的空间来存储数据
    let lesser = [];
    let greater = [];

    //2.1 pivot设置为数组的第一个值
    let pivot = arr[0];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] > pivot) { greater.push(arr[i]) } else { lesser.push(arr[i]) }
    }
    // 3.分别对左右子序列重复前三部的操作，并返回
    return quickSort(lesser).concat(pivot, quickSort(greater));
}

function quickSort2(arr, left, right) {
    if (left < right) {
        let i = left;
        let j = right;
        let pivot = arr[left];
        while (i < j) {
            while (arr[j] > pivot && i < j) {
                j--
            }
            // 在右侧找到小于pivot的值之后，进行位置移动
            arr[i] = arr[j];
            while (arr[i] < pivot && i < j) {
                i++
            }
            // 在左边找到大于pivot的值，将该值移动到右边
            arr[j] = arr[i];
        }
        arr[i] = pivot;
        // 对左右子序列进行相同的步骤
        quickSort2(arr, left, i - 1);
        quickSort2(arr, j + 1, right);
    }
}

const arr = [3, 6, 7, 4, 2, 1, 5]
console.log('输入的数组', arr.toString());
quickSort2(arr, 0, arr.length - 1)
console.log('排序后的数组', arr);